package leetcode每日一题.leetcode20212.滑动窗口;

/**
 * 1. 问题描述
 *      今天，书店老板有一家店打算试营业customers.length分钟。每分钟都有一些顾客（customers[i]）会进入书店，
 *      所有这些顾客都会在那一分钟结束后离开。在某些时候，书店老板会生气。 如果书店老板在第 i 分钟生气，那么grumpy[i] = 1，
 *      否则 grumpy[i] = 0。 当书店老板生气时，那一分钟的顾客就会不满意，不生气则他们是满意的。
 *      书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续X 分钟不生气，但却只能使用一次。
 *      请你返回这一天营业下来，最多有多少客户能够感到满意的数量。
 *
 *      1 <= X <= customers.length == grumpy.length <= 20000
 *      0 <= customers[i] <= 1000
 *      0 <= grumpy[i] <= 1
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/grumpy-bookstore-owner
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 2. 算法分析
 *      分析题意：
 *          从题目中我们知道每天的营业时间：time = customers.length(单位：分钟)
 *          customer数组的含义：customer[i]表示第i分钟进入书店的顾客
 *          grumpy数组的含义：grumpy[i]表示第i分钟书店老板是否生气，
 *              grumpy[i] = 1 表示老板生气，顾客不满意
 *              grumpy[i] = 0 表示老板不生气，顾客满意
 *          老板有一次机会使得自己可以连续X分钟之内不生气(注意只能使用一次)
 *          我们的目的是：求出每天营业下来，最多有多少顾客能够感到满意
 *
 *      从具体例子分析问题：
 *          customer = [1,0,1,2,1,1,7,5]
 *            grumpy = [0,1,0,1,0,1,0,1]
 *                 X = 3
 *          注意到X是一个连续时间，即在customer数组中的一个长度为X的子数组中所有的顾客都可以获得满意
 *          则如果想要满意的顾客最多，老板一定会使用这次机会，并且使用的时机为0,1,2,...,time - X,
 *          整个满意的顾客人数 = 长度为X的子数组中的所有顾客 + 出去X之外的数组中离散的满一个顾客
 *          先试用滑动窗口求出数组中所有长度为X的子数组中的满一个顾客人数，然后再扫描顾客数组，知道出现
 *          老板生气的情况出现，使用上述机会
 *
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class Q003_爱生气的书店老板 {


    /**
     * 滑动窗口 + 暴力    算法没有问题，但是超出时间限制，所以需要进行优化
     */
    public static int maxSatisfied1(int[] customers, int[] grumpy, int X) {
        int res = 0; // 记录全局最大满意的顾客人数
        int time = customers.length; // 每天营业的总时间(分钟为单位)
        int[] Xarr = new int[time-X+1]; // 求出所有长度为X的子数组的顾客人数
        // 使用滑动窗口在O(time)的复杂度内求出Xarr,暴力求出的时间复杂度为O(time * X)
        int left = 0;
        int right = 0;
        int Xsum = 0; // 记录当前长度为X的窗口的总顾客人数
        while(right < time) {
            Xsum += customers[right];
            right++; // 注意：如果right++写在这里，表明我们使用的窗口为左闭右开的区间,即[left,right)
            if (right - left == X) { // 判断当前窗口是否扫描完成
                Xarr[left] = Xsum; // 记录当前窗口的人数
                Xsum -= customers[left]; // 由于下一次进入下一个窗口，所以我们需要减掉当前窗口的左窗口对应的顾客人数
                left++; // 移动左窗口，进入下一个窗口
            }
            if (left == time - X + 1) {
                break;
            }
        }
        // 暴力枚举  时间复杂度为O(time^2)  应该是这里时间爆了
        for (int i = 0; i < time - X + 1; i++) { // 枚举老板使用机会的时机
            int temp = Xarr[i]; // 记录当前枚举的总顾客人数
            for (int j = 0; j < i; j++) {
                if (grumpy[j] == 0) {
                    temp += customers[j];
                }
            }
            for (int j = i + X; j < time; j++) {
                if (grumpy[j] == 0) {
                    temp += customers[j];
                }
            }
            res = Math.max(res,temp);
        }
        return res;
    }

    /**
     * 先求出老板不生气是对应的总的顾客人数，并将此时的顾客数组中的人数设置为0
     * 其次使用滑动窗口求出最大顾客人数
     * 本题实际上是一段离散 + 一段连续，离散的区间无法使用滑动窗口，而连续的区间可以使用滑动窗口解
     * 问题如何转化就是此题的关键
     *
     * 先考虑老板没有技能的时候，则每天满意的顾客直接扫描grumpy数组，求出老板不生气是对应的顾客人数即可
     * 其次当老板有技能的时候，我们只需要进行一定的补偿即可
     */
    public static int maxSatisfied2(int[] customers, int[] grumpy, int X) {
        int out = 0;
        int max = 0;
        int sum = 0;
        for(int i =0;i<grumpy.length;i++) {
            if(grumpy[i]==0) {
                out += customers[i];
                customers[i] = 0;
            }
        }
        int i=0;
        while(i<customers.length) {
            sum += customers[i];
            if(i>=X-1) {
                if(sum >= max) {
                    max = sum;
                }
                sum -= customers[i-X+1];//窗口长度为X,窗口在向前滑动一位之前,需要将窗口中的最左边的一位数减掉
            }
            i++;
        }
        return out+max;
    }


    /**
     * 上述的优化：一次扫描法（没懂含义）
     * @param customers
     * @param grumpy
     * @param X
     * @return
     */
    public static int maxSatisfied3(int[] customers, int[] grumpy, int X) {
        int sum0 = 0; // 记录老板没有生气的总人数
        int compensate = 0; // 记录补偿的最大人数
        int temp = 0; // 记录当前补偿人数
        int left = 0; // 定义左右窗口
        int right = 0;
        int time = customers.length; // 总时间
        while(right < time) {
            // 1. 判断当前老板是否生气，没有生气，加上当前的顾客人数
            sum0 += (grumpy[right] == 0) ? customers[right] : 0;
            // 2. 判断当前老板是否生气，如果生气，加上当前的补偿人数
            temp += (grumpy[right] == 1) ? customers[right] : 0;
            // 移动right
            right++;
            if(right - left > X) { // 扫描完当前长度为X的窗口，即找到了当前窗口的所有补偿人数,并且进入下一个窗口
                temp -= (grumpy[left] == 1) ? customers[left] : 0;
                left++;
            }
            compensate = Math.max(compensate,temp);
        }
        return compensate + sum0;
    }

    // 测试
    public static void main(String[] args) {

    }
}
